"""
题目：判断两棵二叉树是否结构相同且对应节点的值也相同。
"""


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def is_same_tree(p, q):
    """判断两棵二叉树是否相同"""
    # 两棵树都为空，相同
    if not p and not q:
        return True
    # 其中一棵树为空，另一棵不为空，不同
    if not p or not q:
        return False
    # 当前节点值不同，不同
    if p.val != q.val:
        return False
    # 递归判断左子树和右子树分别是否都相同!!!!!!
    return is_same_tree(p.left, q.left) and is_same_tree(p.right, q.right)


# 辅助函数:创建二叉树（复用）
def create_binary_tree(arr):
    if not arr:
        return None
    root = TreeNode(arr[0])
    queue = [root]
    index = 1
    while queue and index < len(arr):
        current = queue.pop(0)
        if arr[index] is not None:
            current.left = TreeNode(arr[index])
            queue.append(current.left)
        index += 1
        if index < len(arr) and arr[index] is not None:
            current.right = TreeNode(arr[index])
            queue.append(current.right)
        index += 1
    return root


# 测试
p = create_binary_tree([1, 2, 3])
q = create_binary_tree([1, 2, 3])
print(is_same_tree(p, q))  # 输出: True

p = create_binary_tree([1, 2])
q = create_binary_tree([1, None, 2])
print(is_same_tree(p, q))  # 输出: False（结构不同）
